<html>
<head>
<link rel="shortcut icon" href="./favicon.ico">
<link rel="stylesheet" type="text/css" href="./style.css">
<link rel="canonical" href="./Divider_Integer_Signed_by_Powers_of_Two.html">
<meta name="viewport" content="width=device-width, initial-scale=1">
<meta name="description" content="While a left shift by N is always equivalent to a multiplication by 2<sup>N</sup> for both signed and unsigned binary integers, an arithmetic shift right by N is only a truncating division by 2<sup>N</sup> for *positive* binary integers. For negative integers, the result is a so-called modulus division, and the quotient ends up off by one in magnitude, and must be corrected by adding +1, *but only if an odd number results as part of the intermediate division steps*.">
<title>Divider Integer Signed by Powers of Two</title>
</head>
<body>

<p class="inline bordered"><b><a href="./Divider_Integer_Signed_by_Powers_of_Two.v">Source</a></b></p>
<p class="inline bordered"><b><a href="./legal.html">License</a></b></p>
<p class="inline bordered"><b><a href="./index.html">Index</a></b></p>

<h1>Signed Integer Divider by Powers of Two (Truncating Division)</h1>
<p>While a left shift by N is always equivalent to a multiplication by
 2<sup>N</sup> for both signed and unsigned binary integers, an arithmetic
 shift right by N is only a truncating division by 2<sup>N</sup> for
 <em>positive</em> binary integers. For negative integers, the result is a so-called
 modulus division, and the quotient ends up off by one in magnitude, and
 must be corrected by adding +1, <em>but only if an odd number results as part
 of the intermediate division steps</em>.</p>
<p>The implementation is based on the PowerPC method, as described in <a
 href="./reading.html#Warren2013">Hacker's Delight</a>, Section 10-1, <em>"Signed
 Division by a Known Power of Two"</em>: We perform the right shift and take
 note if any 1-bits are shifted out. If so, add one to the shifted value.</p>
<p>Since we divide only by powers of two, a division by zero cannot happen.
 (i.e.: there exists no N where 2<sup>N</sup> = 0) Also, we only allow
 positive exponents. A negative exponent would imply a multiplication, and
 that can be done directly with a left shift and not all this complication.</p>
<p>Note that shifting by more than the WORD_WIDTH, with an exponent of value
 greater than WORD_WIDTH, will give a nonsense result for negative numbers
 as we only have WORD_WIDTH sign bits to shift in at most. </p>

<pre>
`default_nettype none

module <a href="./Divider_Integer_Signed_by_Powers_of_Two.html">Divider_Integer_Signed_by_Powers_of_Two</a>
#(
    parameter WORD_WIDTH = 0
)
(
    input  wire signed [WORD_WIDTH-1:0] numerator,
    input  wire        [WORD_WIDTH-1:0] exponent_of_two,

    output wire signed [WORD_WIDTH-1:0] quotient,
    output wire signed [WORD_WIDTH-1:0] remainder
);

    localparam WORD_ZERO = {WORD_WIDTH{1'b0}};
    localparam WORD_ONES = {WORD_WIDTH{1'b1}};
    localparam ONE       = {{WORD_WIDTH-1{1'b0}},1'b1};
</pre>

<p>We depend on automatic width extension of the WORD_WIDTH integer here, as
 doing it using a loop in an initial block is worse for linting and CAD
 warnings.  I normally don't allow automatic width extension, but in this
 case it will always work, as the register will always store up to
 2<sup>N</sup>-1 for a WORD_WIDTH of N, and N is always unsigned.  This
 width extension is necessary to match port widths later on. We do have to
 silence the linter, though.</p>

<pre>
    // verilator lint_off WIDTH
    reg [WORD_WIDTH-1:0] WORD_WIDTH_LONG = WORD_WIDTH;
    // verilator lint_on  WIDTH

    localparam POSITIVE  = 1'b0;
    localparam NEGATIVE  = 1'b1;
</pre>

<p>Prepare for a positive or negative numerator.
 The remainder will also make use of the sign extension.</p>

<pre>
    reg                  numerator_sign = 1'b0;
    reg [WORD_WIDTH-1:0] sign_extension = WORD_ZERO;

    always @(*) begin
        numerator_sign = numerator[WORD_WIDTH-1];
        sign_extension = {WORD_WIDTH{numerator_sign}};
    end
</pre>

<p>Do the initial, uncorrected division.
 The remainder is "short" because all its significant bits are at the left.
 We will shift them, with sign extension, back to the right later.</p>

<pre>
    wire [WORD_WIDTH-1:0] uncorrected_quotient;
    wire [WORD_WIDTH-1:0] short_remainder;

    <a href="./Bit_Shifter.html">Bit_Shifter</a>
    #(
        .WORD_WIDTH         (WORD_WIDTH)
    )
    uncorrected_division
    (
        .word_in_left       (sign_extension),
        .word_in            (numerator),
        .word_in_right      (WORD_ZERO),

        .shift_amount       (exponent_of_two),
        .shift_direction    (1'b1),             // 0/1 -> left/right

        // verilator lint_off PINCONNECTEMPTY
        .word_out_left      (),
        // verilator lint_on  PINCONNECTEMPTY
        .word_out           (uncorrected_quotient),
        .word_out_right     (short_remainder)
    );
</pre>

<p>We need to know if at any point during the shift, a 1-bit was shifted into
 the remainder, indicating an odd-valued intermediate result, and thus an
 off-by-one error in the quotient. A simple OR-reduction works because we
 primed that part of the shift with zeros.</p>

<pre>
    reg odd_intermediate_result = 1'b0;

    always @(*) begin
        odd_intermediate_result = (short_remainder != WORD_ZERO);
    end
</pre>

<p>Now, if the numerator was negative, and there was an odd-valued
 intermediate result, let's add +1 to the uncorrected_quotient to bring it
 back to the result a truncating division would give us.</p>

<pre>
    reg correction = 1'b0;

    always @(*) begin
        correction = (numerator_sign == NEGATIVE) && (odd_intermediate_result == 1'b1);
    end

    <a href="./Adder_Subtractor_Binary.html">Adder_Subtractor_Binary</a>
    #(
        .WORD_WIDTH     (WORD_WIDTH)
    )
    quotient_correction
    (
        .add_sub        (1'b0),    // 0/1 -> A+B/A-B
        .carry_in       (correction),
        .A              (uncorrected_quotient),
        .B              (WORD_ZERO),
        .sum            (quotient),
        // verilator lint_off PINCONNECTEMPTY
        .carry_out      (),
        .carries        (),
        .overflow       ()
        // verilator lint_on  PINCONNECTEMPTY
    );
</pre>

<p>To shift the short remainder back to the right, we need to shift by the
 remainder of the distance to the right, which is WORD_WIDTH
 - exponent_of_two.</p>

<pre>
    wire [WORD_WIDTH-1:0] remainder_shift_amount;

    <a href="./Adder_Subtractor_Binary.html">Adder_Subtractor_Binary</a>
    #(
        .WORD_WIDTH     (WORD_WIDTH)
    )
    remainder_alignment
    (
        .add_sub        (1'b1),    // 0/1 -> A+B/A-B
        .carry_in       (1'b0),
        .A              (WORD_WIDTH_LONG),
        .B              (exponent_of_two),
        .sum            (remainder_shift_amount),
        // verilator lint_off PINCONNECTEMPTY
        .carry_out      (),
        .carries        (),
        .overflow       ()
        // verilator lint_on  PINCONNECTEMPTY
    );
</pre>

<p>Finally, let's shift the remainder significant bits back to the right, with
 the same sign extension as the quotient if the remainder was not zero.</p>

<pre>
    <a href="./Bit_Shifter.html">Bit_Shifter</a>
    #(
        .WORD_WIDTH         (WORD_WIDTH)
    )
    remainder_extension
    (
        .word_in_left       (sign_extension),
        .word_in            (short_remainder),
        .word_in_right      (WORD_ZERO),

        .shift_amount       (remainder_shift_amount),
        .shift_direction    (1'b1),             // 0/1 -> left/right

        // verilator lint_off PINCONNECTEMPTY
        .word_out_left      (),
        .word_out           (remainder),
        .word_out_right     ()
        // verilator lint_on  PINCONNECTEMPTY
    );

endmodule
</pre>

<hr>
<p><a href="./index.html">Back to FPGA Design Elements</a>
<center><a href="https://fpgacpu.ca/">fpgacpu.ca</a></center>
</body>
</html>

